GCD

Definition of GCD

Formal Mathematical Definition

For integers ( a ) and ( b ), not both zero:

$$\gcd(a, b) = \max { d \mid d \text{ divides both } a \text{ and } b }$$

This means the GCD is the largest number that divides both.

Simple Definition

The GCD is the biggest number that divides both numbers exactly.

---

Methods to Calculate GCD

There are several methods to calculate GCD.

---

1. Listing Factors Method

Steps

1. List factors of both numbers
2. Find common factors
3. Choose the largest one

Example: GCD(18, 24)

Factors of 18:

$$1, 2, 3, 6, 9, 18$$

Factors of 24:

$$1, 2, 3, 4, 6, 8, 12, 24$$

Common factors:

$$1, 2, 3, 6$$

GCD:

$$\boxed{6}$$

---

2. Prime Factorization Method

Steps

1. Find prime factors
2. Multiply common prime factors

Example: GCD(24, 36)

Prime factors of 24:

$$24 = 2^3 \times 3$$

Prime factors of 36:

$$36 = 2^2 \times 3^2$$

Common factors:

$$2^2 \times 3$$

GCD:

$$= 4 \times 3$$ $$= \boxed{12}$$

---

3. Euclidean Algorithm

This is the most efficient method.

Formula:

$$\gcd(a, b) = \gcd(b, a \bmod b)$$

Example: GCD(48, 18)

Step 1:

$$48 \div 18 = 2 \text{ remainder } 12$$

Step 2:

$$18 \div 12 = 1 \text{ remainder } 6$$

Step 3:

$$12 \div 6 = 2 \text{ remainder } 0$$

GCD:

$$\boxed{6}$$

---

4. Division Method

This is similar to the Euclidean algorithm.

Example: GCD(56, 42)

Step 1:

$$56 \div 42 = 1 \text{ remainder } 14$$

Step 2:

$$42 \div 14 = 3 \text{ remainder } 0$$

GCD:

$$\boxed{14}$$

---

5. Repeated Subtraction Method

Subtract smaller number from larger until equal.

Example: GCD(15, 9)

Step 1:

$$15 - 9 = 6$$

Now find GCD(9, 6)

Step 2:

$$9 - 6 = 3$$

Now find GCD(6, 3)

Step 3:

$$6 - 3 = 3$$

Now both equal.

GCD:

$$\boxed{3}$$

---

6. Using Recursion (Programming Method)

Recursive formula:

gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

Example: GCD(24, 18)

Step 1:

$$gcd(24, 18)$$

Step 2:

$$gcd(18, 6)$$

Step 3:

$$gcd(6, 0)$$

Result:

$$\boxed{6}$$

---

Important Properties of GCD

These properties are very useful.

---

Property 1: Commutative Property

$$\gcd(a, b) = \gcd(b, a)$$

Example:

$$\gcd(12, 18) = \gcd(18, 12) = 6$$

---

Property 2: GCD with Zero

$$\gcd(a, 0) = |a|$$ $$\gcd(0, b) = |b|$$ $$\gcd(0, 0) = 0$$

Example:

$$\gcd(10, 0) = 10$$

---

Property 3: Product Relationship with LCM

$$\gcd(a, b) \times \text{lcm}(a, b) = a \times b$$

Example:

$$\gcd(6, 8) = 2$$ $$\text{lcm}(6, 8) = 24$$ $$2 \times 24 = 48$$ $$6 \times 8 = 48$$

Correct.

---

Property 4: If a divides b

If:

$$a \mid b$$

Then:

$$\gcd(a, b) = a$$

Example:

$$\gcd(5, 20) = 5$$

---

Property 5: GCD of Co-prime Numbers

If numbers are co-prime:

$$\gcd(a, b) = 1$$

Example:

$$\gcd(8, 15) = 1$$

---

Property 6: Associative Property

$$\gcd(a, b, c) = \gcd(\gcd(a, b), c)$$

Example:

$$\gcd(12, 18, 24)$$

Step 1:

$$\gcd(12, 18) = 6$$

Step 2:

$$\gcd(6, 24) = 6$$

---

Property 7: Linear Combination Property

If:

$$d = \gcd(a, b)$$

Then:

$$d \mid (ax + by)$$

for any integers ( x ) and ( y ).

Example:

$$\gcd(6, 9) = 3$$ $$3 \mid (6 \times 2 + 9 \times 1 = 21)$$

True.

---

Property 8: GCD is Always Positive

$$\gcd(a, b) \ge 0$$

---

Property 9: Divisibility Property

$$\gcd(a, b) \mid a$$ $$\gcd(a, b) \mid b$$

(The GCD divides both numbers.)

---

Property 10: Euclidean Property

$$\gcd(a, b) = \gcd(a, b - a)$$

More generally:

$$\gcd(a, b) = \gcd(a, b \bmod a)$$

---

Property 11: Scaling Property

For any integer ( k \ne 0 ):

$$\gcd(ka, kb) = |k| \gcd(a, b)$$

---

Property 12: Multiplicative Property (when coprime)

If:

$$\gcd(a, b) = 1$$

Then:

$$\gcd(a, bc) = \gcd(a, c)$$

---

Property 13: Important Coprime Property

If:

$$\gcd(a, b) = 1$$

and

$$a \mid bc$$

Then:

$$a \mid c$$

---

Property 14: Relation with Powers

$$\gcd(a^m, a^n) = a^{\min(m, n)}$$

Applications of GCD

2. Solving Diophantine Equations

Example:

$$6x + 9y = 3$$

Solution exists because:

$$\gcd(6, 9) = 3$$

5. Geometry Problems

Finding largest square tile size.

Example:

Rectangle:

12 × 18

GCD = 6

Largest square tile = 6 × 6

Common Mistakes Students Make

Mistake 1: Confusing GCD with LCM

GCD = Largest common divisor LCM = Smallest common multiple

Mistake 3: Stopping Euclidean Algorithm Early

Must continue until remainder = 0.

Key Points:

• Euclidean algorithm is the most efficient